04 快速选择算法

快速选择算法（quickselect）

快速选择算法用于解决Top-K问题（在数组中找到第k大的元素）。

采用快速排序的思想，每次选取一个元素作为主元，将比它小的元素放在左侧，比它大的元素放在右侧。此时，如果主元是第k个元素，则直接返回；否则，选取对应区间继续迭代。这种算法的渐进时间复杂度是$O(n)$。

实现细节

在快排时，不同分区方式也会对时间复杂度产生影响。

最简单的排序方法是从头开始遍历，如果某个元素小于主元，则和主元交换位置。这种方式会带来大量重复。

解决这一问题可以采用Hoare分区。注意Hoare分区后，主元的位置是不确定的。

int i = l - 1, j = r + 1;
int partition = nums[l];
while (i < j) {
    do { i++; } while (nums[i] < partition);
    do { j--; } while (nums[i] > partition);
    if (i < j) {
        swap(nums[i], nums[j]);
    }
}
if (j < k) {
    l = j + 1;
} else {
    r = j;
}

具体来说，在进行分区后，i指向第一个大于等于主元的元素位置，j指向第一个小于等于主元的元素位置，i、j都不一定指向主元。也就是说，即使此时j和k相等，nums[k]也不一定是正确答案，因为有可能j不是主元，而小于主元的区域还未排序。以上的划分方式保证了下一次迭代一定会包含正确的位置。

此外，不能采用类似以下的写法

while (i <= j && nums[i] < partition) {
    i++;
}

这种写法会让i多次向右扩展，增大了主元被划分在数组两侧的概率。快排中，主元越靠近中心效率越高，这种写法会增大时间复杂度。

完整代码

以下是力扣215题答案。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            int i = l - 1, j = r + 1;
            int partition = nums[l];
            while (i < j) {
                while (i <= j && nums[i] <= partition) i++;
                while (i <= j && nums[j] >= partition) j--; 
                if (i < j) {
                    swap(nums[i], nums[j]);
                }
            }

            if (j < nums.size() - k) {
                l = j + 1;
            } else {
                r = j;
            }
        }

        return nums[l];
    }
};